 
import java.util.*;
import java.lang.Math;
import java.awt.*;
import java.applet.*;

public class Tree {
	public final int ERR = -12;
	public Board board;
	public Vector<node> visitedNodes = new Vector<node>();
	public int num_tile;	// num tiles of puzzle
	public int count = 0;
	public int player = 0;
	Long lStartTime;
	Long maxTime;
	
	public class move {
		public move(int _x, int _y, int _p) 
		{
			x = _x;
			y = _y;
			player = _p;
		}
		int x, y, player;
	}
	
	// node structure
	public class node {
		// default to the easy state with no depth
		public node(int s, int p) 
		{ 
			int size = s;
			int[][] state = new int[size][size];
			for(int i = 0; i < size; i++)
				for(int j = 0; j < size; j++)
					state[i][j] = 0;
			board = new Board(s);
			board.board = state;
			h = 0; 
			depth = 0; 
			costToNode = 0;
			player = p;
			parent = null;
		}
		public node( Board b, int p, int hin, int din, Vector<move> cp)
		{
			board = new Board(b.size);
			board.copy(b);
			h = hin;
			depth = din;
			cur_path = cp;
			costToNode = 0;
			player = p;
			parent = null;
		}
		Board board;
		node parent;
		public int h;
		public int player;
		public int depth;
		public int costToNode;
		public Vector<move> cur_path;
	}
	
	Tree()
	{
	}
	
	public void init() {
		/*int state[] = {1, 3, 4, 8, 6, 2, 7, 0, 5};	// Easy
		Vector<op> ops = new Vector<op>();		
		node n = new node(state, 0, 0, ops);
		
		n = idastar(n, 4);	// IDA*
		
		// display visited nodes
		for(int i = 0; i < visitedNodes.size(); i++)
		{
			printTile(visitedNodes.get(i).state);
			//System.out.println();
		}*/
	}

	public void paint(Graphics g) {
		
		
		////System.out.println(n.state[4] + " " + n.h + " " + n.cur_path.get(1));
		g.drawString("Welcome to Java!!", 50, 60 );
	}
	
	// IDA* Stuff
	// ----------------------------------------------------------------------------
	public int max_depth = 0;
	// idastar-core: search for a leaf node and return the value
	// try this with different trees.
	private node idastar_core(Vector<node> nodeList, int hu_limit, int numMoves)
	{
		//static node orig = nodeList.front();
		//cout << "loading...\n";
		if( nodeList.size() != 0 )
		{
			node cur_node = nodeList.firstElement();
			nodeList.remove(0);
			//System.out.println("cur");
			//printTile(cur_node.board.board, cur_node.board.size);
			//System.out.println("end cur");
			//System.out.println("DEPTH!- " + cur_node.depth + " nm " + nodeList.size());
			
			if(System.currentTimeMillis()-lStartTime >= maxTime)
			{
				System.out.println("time sucks: " + (System.currentTimeMillis()-lStartTime));
				return cur_node;
			}
			
			if(cur_node.depth > 5){
				System.out.println("depth " + nodeList.size());
				int max = 0;
				for(int i = 0; i < nodeList.size(); i++)
				{
					if(nodeList.get(i).h > max)
					{
						max = nodeList.get(i).h;
						System.out.println("max: " + max);
						cur_node = nodeList.get(i);
					}
				}
				System.out.println("c: " + cur_node.h);
				return cur_node;
			}
			
			if(cur_node.board.someoneWon() != 0 && nodeList.size() == 0)
			{
				System.out.println("finish found" + cur_node.cur_path);
				printTile(cur_node.board.board, cur_node.board.size);
				return cur_node;
			}
			
			//Vector<node> tmpNodeList = new Vector<node>(nodeList.subList(it, nodeList.size()));
			if( goalp(cur_node) )
			{
				System.out.println("goal found!");
				return cur_node;
			}
			else
			{
				//node tmpNode = new node(cur_node.state, cur_node.size, cur_node.h, cur_node.depth, cur_node.cur_path);
				Vector<node> tl;
				try {
					tl = expandstar(cur_node, visitedNodes);
				}
				catch( StackOverflowError e ) {
					System.out.println("Stack Overflow " + cur_node.depth);
					return cur_node;
				}
	
				int[] hus = new int[tl.size()];
				for(int i = 0; i < tl.size(); i++)
					hus[i] = tl.get(i).h;
	
				// sort from lowest to highest, then reverse the array
				Arrays.sort(hus);
				for (int left=0, right=hus.length-1; left<right; left++, right--) {
				    // exchange the first and last
				    int temp = hus[left]; hus[left]  = hus[right]; hus[right] = temp;
				}
				//System.out.println("hues " + tl.size());
				System.out.println("h1: " + hus[0] + " h2: " + hus[tl.size()-1]);
				for(int i = 0; i < tl.size(); i++)	// hus loop - it is the same size as tl
				{
					
					// new way
					// not only check which tl value to add, but also make sure that its hueristic minus the parents is less than the hueristic limit
					//for(int j = 0; j < tl.size(); j++)
						//if( (hus[i]-cur_node.costToNode) < hu_limit )
						//	tmpNodeList.add(tl.get(i));
					
					// old way
					for(int j = 0; j < tl.size(); j++)
					{
						System.out.println(i + " hut " + ((hus[i]-cur_node.costToNode) < hu_limit));
						if( (tl.get(j).h == hus[i]) )// && (hus[i]-cur_node.costToNode) < hu_limit )
						{
							System.out.println(i + " HAT: " + hus[i]);
							nodeList.add(0, tl.get(j));
							//visitedNodes.add(tl.get(j));
							tl.remove(j);
							break;
						}
					}
				}
				
				//player = -player;
	
				if( nodeList.size() > max_depth )
					max_depth = nodeList.size();
				
				////System.out.println("TREE SIZE: " + visitedNodes.size());
				// display visited nodes
				/*//System.out.println("nodes!!");
				for(int i = 0; i < tmpNodeList.size(); i++)
				{
					printTile(board.board);//tmpNodeList.get(i).state);
					//System.out.println();
				}
				//System.out.println("end nodes!!");*/
	
				return idastar_core(nodeList, hu_limit, numMoves);
	
			}
	
		}
		// clear the visitedNodes for same reason as ids
		//visitedNodes.clear();
		//System.out.println("NOOOOOO");
		node ret = new node(board.size, 0);
		ret.board.board[0][0] = ERR;
		return ret;
	
	}
	
	private node idastar_core_bad(Vector<node> nodeList, int hu_limit, int numMoves)
	{
		//static node orig = nodeList.front();
		//cout << "loading...\n";
		if( nodeList.size() != 0 )
		{
			node cur_node = nodeList.firstElement();
			nodeList.remove(0);
			//System.out.println("cur");
			//printTile(cur_node.board.board, cur_node.board.size);
			//System.out.println("end cur");
			//System.out.println("DEPTH!- " + cur_node.depth + " nm " + nodeList.size());
			
			if(System.currentTimeMillis()-lStartTime >= maxTime)
			{
				System.out.println("time sucks: " + (System.currentTimeMillis()-lStartTime));
				return cur_node;
			}
			
			if(cur_node.depth > 5){
				System.out.println("depth " + nodeList.size());
				int max = 0;
				for(int i = 0; i < nodeList.size(); i++)
				{
					if(nodeList.get(i).h > max)
					{
						max = nodeList.get(i).h;
						System.out.println("max: " + max);
						cur_node = nodeList.get(i);
					}
				}
				System.out.println("c: " + cur_node.h);
				return cur_node;
			}
			
			if(cur_node.board.someoneWon() != 0 && nodeList.size() == 0)
			{
				System.out.println("finish found" + cur_node.cur_path);
				printTile(cur_node.board.board, cur_node.board.size);
				return cur_node;
			}
			
			//Vector<node> tmpNodeList = new Vector<node>(nodeList.subList(it, nodeList.size()));
			if( goalp(cur_node) )
			{
				System.out.println("goal found!");
				return cur_node;
			}
			else
			{
				//node tmpNode = new node(cur_node.state, cur_node.size, cur_node.h, cur_node.depth, cur_node.cur_path);
				Vector<node> tl;
				try {
					tl = expandstar(cur_node, visitedNodes);
				}
				catch( StackOverflowError e ) {
					System.out.println("Stack Overflow " + cur_node.depth);
					return cur_node;
				}
	
				int[] hus = new int[tl.size()];
				for(int i = 0; i < tl.size(); i++)
					hus[i] = tl.get(i).h;
	
				// sort from lowest to highest, then reverse the array
				Arrays.sort(hus);
				//System.out.println("hues " + tl.size());
				System.out.println("h1: " + hus[0] + " h2: " + hus[tl.size()-1]);
				for(int i = 0; i < tl.size(); i++)	// hus loop - it is the same size as tl
				{
					
					// new way
					// not only check which tl value to add, but also make sure that its hueristic minus the parents is less than the hueristic limit
					//for(int j = 0; j < tl.size(); j++)
						//if( (hus[i]-cur_node.costToNode) < hu_limit )
						//	tmpNodeList.add(tl.get(i));
					
					// old way
					for(int j = 0; j < tl.size(); j++)
					{
						System.out.println(i + " hut " + ((hus[i]-cur_node.costToNode) < hu_limit));
						if( (tl.get(j).h == hus[i]) )// && (hus[i]-cur_node.costToNode) < hu_limit )
						{
							System.out.println(i + " HAT: " + hus[i]);
							nodeList.add(0, tl.get(j));
							//visitedNodes.add(tl.get(j));
							tl.remove(j);
							break;
						}
					}
				}
				
				//player = -player;
	
				if( nodeList.size() > max_depth )
					max_depth = nodeList.size();
				
				////System.out.println("TREE SIZE: " + visitedNodes.size());
				// display visited nodes
				/*//System.out.println("nodes!!");
				for(int i = 0; i < tmpNodeList.size(); i++)
				{
					printTile(board.board);//tmpNodeList.get(i).state);
					//System.out.println();
				}
				//System.out.println("end nodes!!");*/
	
				return idastar_core(nodeList, hu_limit, numMoves);
	
			}
	
		}
		// clear the visitedNodes for same reason as ids
		//visitedNodes.clear();
		//System.out.println("NOOOOOO");
		node ret = new node(board.size, 0);
		ret.board.board[0][0] = ERR;
		return ret;
	
	}
	
	// idastar wrapper interface
	public node idastar(Board b, int hu_limit, int p, int numMoves, Long maxtime)
	{
		lStartTime = System.currentTimeMillis();
		maxTime = maxtime;
		board = new Board(b.size);
		board.copy(b);
		player = p;
		//System.out.println("in");
		int[] state = new int[b.size*b.size];
		int cnt = 0;
		for(int i = 0; i < b.size; i++)
		{
			for(int j = 0; j < b.size; j++)
			{
				state[cnt] = b.board[i][j];
				//System.out.print(state[cnt] + " ");
				cnt++;
			}
			//System.out.println();
		}
		//System.out.println("end in");
		Vector<move> xys = new Vector<move>();
		Tree.node n = new Tree.node(b, p, 0, 0, xys);
		
		Vector<node> node_list = new Vector<node>();
		node_list.add(n);
		node result = idastar_core(node_list, hu_limit, numMoves);
	
		// call until idastar_core returns a valid node, and increase the hueristic limit each time it fails
		while( isNull(result) )
		{
			if(hu_limit > 5000)
				return result;
			Vector<node> node_list2 = new Vector<node>();
			node_list2.add(n);
			System.out.println("null " + hu_limit);
			result = idastar_core(node_list2, hu_limit++, numMoves);
		}
	
		return result;
	}
	// idastar wrapper interface
	public node idastarbad(Board b, int hu_limit, int p, int numMoves, Long maxtime)
	{
		lStartTime = System.currentTimeMillis();
		maxTime = maxtime;
		board = new Board(b.size);
		board.copy(b);
		player = p;
		//System.out.println("in");
		int[] state = new int[b.size*b.size];
		int cnt = 0;
		for(int i = 0; i < b.size; i++)
		{
			for(int j = 0; j < b.size; j++)
			{
				state[cnt] = b.board[i][j];
				//System.out.print(state[cnt] + " ");
				cnt++;
			}
			//System.out.println();
		}
		//System.out.println("end in");
		Vector<move> xys = new Vector<move>();
		Tree.node n = new Tree.node(b, p, 0, 0, xys);
		
		Vector<node> node_list = new Vector<node>();
		node_list.add(n);
		node result = idastar_core_bad(node_list, hu_limit, numMoves);
	
		// call until idastar_core returns a valid node, and increase the hueristic limit each time it fails
		while( isNull(result) )
		{
			if(hu_limit > 5000)
				return result;
			Vector<node> node_list2 = new Vector<node>();
			node_list2.add(n);
			System.out.println("null " + hu_limit);
			result = idastar_core(node_list2, hu_limit++, numMoves);
		}
	
		return result;
	}
	/*public node idastar(node initial_node, int hu_limit)
	{
		Vector<node> node_list = new Vector<node>();
		node_list.add(initial_node);
		node result = idastar_core(node_list, hu_limit);
	
		// call until idastar_core returns a valid node, and increase the hueristic limit each time it fails
		while( isNull(result) )
			result = idastar_core(node_list, hu_limit++);
	
		return result;
	}*/
	
	// ------------------------------------------------------------------------------
	// gets the hueristic by adding the places that each value is out of place
	// ------------------------------------------------------------------------------
	/*private int h(int state[])
	{
		// if a value is out of place, it then sees how far the manhattan distance is to the correct place, and adds it to the hueristic
		int hu = 0;
		for(int i = 0; i < num_tile; i++)
			if( state[i] != goal[i] )
				hu += Math.abs( (i/3) - (location(state[i], goal)/3) ) + Math.abs( (i%3) - (location(state[i], goal)%3) );
	
		return hu;
	}*/
	
	//-------------------------------------------------------------------------------
	// find location of number in state (0 1 2 3 4 .. 8)
	//-------------------------------------------------------------------------------
	private int location( int num, int state[] )
	{
		for(int i = 0; i < num_tile; i++)
			if(state[i] == num)
				return i;
	
		return -1;
	
	}
	
	//-------------------------------------------------------------------------------
	// Swap values in two locations
	//-------------------------------------------------------------------------------
	private int[] mySwap( int loc1, int loc2, int state[] )
	{
		int[] tmp = new int[num_tile];
		for(int i = 0; i < num_tile; i++)
			tmp[i] = state[i];
		int val = tmp[loc1];
		tmp[loc1] = tmp[loc2];
		tmp[loc2] = val;
	
		return tmp;	// return new board state
	
	}
	
	//-------------------------------------------------------------------------------
	// Look if op is applicable to state
	//-------------------------------------------------------------------------------
	/*private boolean applicable( op o, node n )
	{
		switch(o)
		{
		case UP:
			if( location(0, n.state) < 3 )
				return false;
			break;
	
		case DOWN:
			if( location(0, n.state) > 5 )
				return false;
			break;
	
		case LEFT:
			if( location(0, n.state) % 3 == 0 )
				return false;
			break;
	
		case RIGHT:
			if( (location(0, n.state) - 2) % 3 == 0 )
				return false;
			break;
	
		}
		return true;
	
	}*/
	
	//-------------------------------------------------------------------------------
	// Apply op to state using A*
	//-------------------------------------------------------------------------------
	/*private node applyOPstar(op o, node n)
	{
		node tmp = new node(n.state, n.h, n.depth, n.cur_path);
		int[] var = new int[num_tile];
		int blank = location(0, tmp.state);
		int g = tmp.h;
		////System.out.println(blank);
		switch(o)
		{
		case UP:
			var = mySwap(blank, blank-3, tmp.state);
			break;
	
		case DOWN:
			var = mySwap(blank, blank+3, tmp.state);
			break;
	
		case LEFT:
			var = mySwap(blank, blank-1, tmp.state);
			break;
	
		case RIGHT:
			var = mySwap(blank, blank+1, tmp.state);
			break;
	
		}
		tmp.cur_path.add(o);
		tmp.depth += 1;
		for(int i =0; i < num_tile; i++)
			tmp.state[i] = var[i];
		// astar uses both the cost to the new node, plus the cost to the parent node
		tmp.h = h(tmp.state) + g;
		tmp.costToNode = tmp.h;
	
		//delete var;
		return tmp;
	
	}*/
	public node applyOPstar(int x, int y, node n)
	{
		Board boardTmp = new Board(board.size);
		boardTmp.copy(n.board);
		node tmp = new node(boardTmp, n.player, n.h, n.depth, n.cur_path);
		//int blank = location(0, tmp.state);
		int g = tmp.h;
		node parent = tmp.parent;
		tmp.board.insertPiece(x, y, tmp.player);
		
		//System.out.println("step: " + tmp.player);
		//System.out.println("bl: " + tmp.board.numBlack + " wh: " + tmp.board.numWhite);
		//printTile(tmp.board.board, tmp.board.size);
		//System.out.println("end step");
		
		//int[] xy = new int[2];
		//xy[0] = x; xy[1] = y;
		move m = new move(x, y, tmp.player);
		tmp.cur_path.add(m);
		//System.out.println("t: " + tmp.cur_path);
		tmp.depth += 1;
		tmp.parent = parent;
		// astar uses both the cost to the new node, plus the cost to the parent node
		tmp.h = evaluateBoard(tmp.board, tmp) + g;
		tmp.player = -tmp.player;
		//System.out.println("depth " + tmp.depth);
		//System.out.println("hue - " + tmp.h);
		tmp.costToNode = tmp.h;
	
		//delete var;
		return tmp;
	
	}
	
	//-------------------------------------------------------------------------------
	// Print result 
	//-------------------------------------------------------------------------------
	private void printResult( node n )
	{
		/*//System.out.print("Path: (");
		for(int i = 0; i < n.cur_path.size(); i++)
			//System.out.print(n.cur_path.get(i) + " ");
		//System.out.print(")\n");
	
		//System.out.println("Depth: " + n.depth);*/
	
	}
	
	//-------------------------------------------------------------------------------
	// Print puzzle 
	//-------------------------------------------------------------------------------
	public void printTile( int state[][], int s )
	{
		/*for(int i =0; i < num_tile/3; i++)
			//System.out.print(state[i] + " ");
		//System.out.println();
	
		for(int i = num_tile/3; i < 2*num_tile/3; i++)
			//System.out.print(state[i] + " ");
		//System.out.println();
	
		for(int i = 2*num_tile/3; i < num_tile; i++)
			//System.out.print(state[i] + " ");
		//System.out.println();*/
		for(int i =0; i < s; i++)
		{
			for(int j =0; j < s; j++)
			{
				if(state[i][j] == 1 || state[i][j] == 0)
					System.out.print(" " + state[i][j] + " ");
				else
					System.out.print(state[i][j] + " ");
			}
			System.out.println();
		}
	
	}
	public void printTile( int state[] )
	{
		int cnt = 0;
		for(int i =0; i < board.size; i++)
		{
			for(int j =0; j < board.size; j++)
			{
				//System.out.print(state[cnt] + " ");
				cnt++;
			}
			//System.out.println();
		}
	
	}
	
	//-------------------------------------------------------------------------------
	// Print answer
	//-------------------------------------------------------------------------------
	private void printAnswer( node n )
	{
		/*printTile(n.state);
		//System.out.println();
	
		int size = n.cur_path.size();
		for(int i =0; i < size; i++)
		{
			n = applyOPstar(n.cur_path.get(i), n);
			printTile(n.state);
			//System.out.println();
		}*/
	
	}
	
	//-------------------------------------------------------------------------------
	// Check if current state is goal state
	//-------------------------------------------------------------------------------
	/*private boolean goalp( node n )
	{
		for(int i = 0; i < num_tile; i++)
			if( n.state[i] != goal[i] )
				return false;
	
		return true;
	
	}*/
	private boolean goalp( node n )
	{
		if(n.board.someoneWon() == player)	// white won
		{
			//System.out.println("winner - b: " + n.board.numBlack + " w: " + n.board.numWhite);
			//printTile(n.board.board, n.board.size);
			return true;
		}
		
		return false;
	}
	
	//-------------------------------------------------------------------------------
	// check for duplicate states
	//-------------------------------------------------------------------------------
	/*private boolean dupe( int state[], Vector<node> nodes )
	{
		////System.out.println(nodes.size());
		for(int i = 0; i < nodes.size(); i++)
		{
			boolean eq = true;
			for(int j = 0; j < num_tile; j++)
				if( state[j] != nodes.get(i).state[j] ){
					eq = false;
					break;
				}
			if( eq )
				return true;
		}
	
		return false;
	
	}*/
	
	//-------------------------------------------------------------------------------
	// call a function to expand - astar
	//-------------------------------------------------------------------------------
	private Vector<node> expandstar( node n, Vector<node> nodes )
	{
		//cout << "\n\nEXPAND!!\n\n";
		Vector<node> tmp = new Vector<node>();
	
		/*if(board.noMoreValidMoves(player) == true)
		{
			int[] xy = new int[2];
			xy[0] = -1; xy[1] = 0;
			n.cur_path.add(xy);
			return n;
		}*/
		System.out.println("cur:");
		printTile(n.board.board, n.board.size);
		System.out.println("end cur");
		if(n.board.noMoreValidMoves(n.player))
		{
			System.out.println("no p");
			if(n.board.noMoreValidMoves(-n.player))
			{
				System.out.println("no -p");
				return tmp;	//no moves left
			}
			else
			{
				//System.out.println("p: " + n.player);
				n.player = -n.player; // the other player can move
				//System.out.println("p2: " + n.player);
			}
		}
		
		int cnt = 0;
		for(int i = 0; i < n.board.size; i++)
		{
			for(int j = 0; j < n.board.size; j++)
			{
				//System.out.println("i: " + i + " j: " + j + " p: " + n.player + " m: " + n.board.isValidMove(i, i, n.player));
				if(n.board.isValidMove(i, j, n.player))
				{
					//System.out.println("why?: " + i + " " + j);
					tmp.add(applyOPstar(i, j, n));
					System.out.println("step: " + cnt);
					printTile(tmp.get(tmp.size()-1).board.board, tmp.get(tmp.size()-1).board.size);
					System.out.println("end step");
					//player = -player;
					cnt++;
					if(goalp(tmp.get(tmp.size()-1)))	// goal reached
					{
						System.out.println("tmp foun " + tmp);
						return tmp;
					}
						
					
				}
			}
		}
		/*//System.out.println("tmp");
		printTile(tmp.get(tmp.size()-1).state);
		//System.out.println("end tmp");*/
		
		/*// Debug - print out node list
		//System.out.println("NODE LIST");
		for(int i = 0; i < nodes.size(); i++){
			printTile(nodes.get(i).state);
			printResult(nodes.get(i));
		}
		//System.out.println("END NODE LIST");
	
		// Debug - view values to be added to node list
		for(int i = 0; i < tmp.size(); i++){
			printTile(tmp.get(i).state);
			////System.out.println("HUE: " + (tmp.get(i).h-n.costToNode));
			printResult(tmp.get(i));
	
			// used to view step by step
			//getch();
		}*/
	
		//cout << "\n\nEND EXPAND";
		
	
		return tmp;
	
	}
	
	// test a nodes validity - used to check if the iterative deepening algos fail
	// ------------------------------------------------------------------------------
	public boolean isNull(node n)
	{
		// fail vector = -1 3 4
		//				  8 6 2
		//				  7 0 5
		/*if( n.state[0] == -1 && n.state[1] == 3 && n.state[2] == 4 && n.state[3] == 8 && n.state[4] == 6 && n.state[5] == 2 && n.state[6] == 7 &&
			n.state[7] == 0 && n.state[8] == 5 )
			return true;*/
		if(n.board.board[0][0] == ERR)
			return true;
	
		return false;
	
	}
	
	//returns array containing 2 elements
	//equal to number of moves for each player
	//[0] = number of black moves
	//[1] = number of white moves
	public int[] mobileCount(Board aBoard)
	{
		int numMoves[] = new int[2];
		int numBlack = 0;
		int numWhite = 0;
		for(int i =0; i< board.size; i++)
		{
			for(int j = 0; j<board.size; j++)
			{
				if(aBoard.isValidMove(i,j, 1))
				{
					numBlack++;
				}
			}
		}
		numMoves[0] = numBlack;
		numMoves[1] = numWhite;
		return numMoves;
	}
	
	public int[] stableCount(Board aBoard)
	{
		int stable[] = new int[2];
		return stable;
		
	}
	
	//returns a number (usually) between -100 and 100 depending on board state
	//can be higher or lower for very good/bad board states
	public int evaluateBoard(Board aBoard, node n)
	{
		/*System.out.println("step: " + n.player);
		//System.out.println("bl: " + tmp.board.numBlack + " wh: " + tmp.board.numWhite);
		printTile(aBoard.board, aBoard.size);
		System.out.println("end step");*/
		
		//find the mobility
		int mobilityRating;
		int boardValue = 0;
		int mobility[] = mobileCount(aBoard);
		int myMobility =0;
		int opponentsMobility = 0;
		if(n.player==1 )
		{
			myMobility = mobility[0];
			opponentsMobility = mobility[1];
			
		}
		else
		{
			myMobility = mobility[1];
			opponentsMobility = mobility[0];
		}
		
		int relativeMobility = myMobility - opponentsMobility;
		mobilityRating = relativeMobility; //mobility weight
		
		
		
		//piece rating calculations
		
		int pieceRating = 0;
		int pieceDifference = 0;
		int myPieces =0;
		int opponentsPieces = 0;
		
		if(n.player==1 )
		{
			myPieces = aBoard.numBlack;
			opponentsPieces = aBoard.numWhite;
			
		}
		else
		{  
			myPieces = aBoard.numWhite;
			opponentsPieces = aBoard.numBlack;
		}
		pieceDifference = myPieces - opponentsPieces;
		
		pieceRating = pieceDifference;
		
		
		//calculate corner rating
		
		int cornerRating = 0;
		Boolean firstCorner = false;
		Boolean firstXsquare = false;
		Boolean secondCorner = false;
		Boolean secondXsquare = false;
		Boolean thirdCorner = false;
		Boolean thirdXsquare = false;
		Boolean fourthCorner = false;
		Boolean fourthXsquare = false;
		
		Boolean ofirstCorner = false;
		Boolean ofirstXsquare = false;
		Boolean osecondCorner = false;
		Boolean osecondXsquare = false;
		Boolean othirdCorner = false;
		Boolean othirdXsquare = false;
		Boolean ofourthCorner = false;
		Boolean ofourthXsquare = false;
		
		int myCorners = 0;
		int opponentsCorners = 0;
		int cornerDifference = 0;;
		
		
		if(n.player == 1)
		{
			//my corners
			if(aBoard.board[0][aBoard.size-1] == 1)
			{
				firstCorner = true;
				myCorners++;
			}
			if(aBoard.board[1][aBoard.size-2] == 1)
			{
				 firstXsquare = true;
			}
			
			if(aBoard.board[aBoard.size-1][0] == 1)
			{
				myCorners++;
				secondCorner = true;
			}
			if(aBoard.board[aBoard.size-2][1] == 1)
			{
				secondXsquare = true;
			}
			
			if(aBoard.board[0][0] == 1)
			{
				myCorners++;
				thirdCorner = true;
			}
			if(aBoard.board[1][1] == 1)
			{
				thirdXsquare = true;
			}
			
			if(aBoard.board[aBoard.size-1][aBoard.size-1] == 1)
			{
				myCorners++;
				fourthCorner = true;
			}
			if(aBoard.board[aBoard.size-2][aBoard.size-2] == 1)
			{
				fourthXsquare = true;
			}
			
			//opponents corners
			if(aBoard.board[0][aBoard.size-1] == -1)
			{
				ofirstCorner = true;
				opponentsCorners++;
			}
			if(aBoard.board[1][aBoard.size-2] == -1)
			{
				 ofirstXsquare = true;
			}
			
			if(aBoard.board[aBoard.size-1][0] == -1)
			{
				opponentsCorners++;
				osecondCorner = true;
			}
			if(aBoard.board[aBoard.size-2][1] == -1)
			{
				secondXsquare = true;
			}
			
			if(aBoard.board[0][0] == -1)
			{
				opponentsCorners++;
				othirdCorner = true;
			}
			if(aBoard.board[1][1] == -1)
			{
				othirdXsquare = true;
			}
			
			if(aBoard.board[aBoard.size-1][aBoard.size-1] == -1)
			{
				opponentsCorners++;
				ofourthCorner = true;
			}
			if(aBoard.board[aBoard.size-2][aBoard.size-2] == -1)
			{
				ofourthXsquare = true;
			}
				
		}
		else if(n.player == -1)
		{
			//my corners
			if(aBoard.board[0][aBoard.size-1] == -1)
			{
				myCorners++;
				firstCorner = true;
			}
			if(aBoard.board[1][aBoard.size-2] == -1)
			{
				 firstXsquare = true;
			}
			
			if(aBoard.board[aBoard.size-1][0] == -1)
			{
				myCorners++;
				secondCorner = true;
			}
			if(aBoard.board[aBoard.size-2][1] == -1)
			{
				secondXsquare = true;
			}
			
			if(aBoard.board[0][0] == -1)
			{
				myCorners++;
				thirdCorner = true;
			}
			if(aBoard.board[1][1] == -1)
			{
				thirdXsquare = true;
			}
			
			if(aBoard.board[aBoard.size-1][aBoard.size-1] == -1)
			{
				myCorners++;
				fourthCorner = true;
			}
			if(aBoard.board[aBoard.size-2][aBoard.size-2] == -1)
			{
				fourthXsquare = true;
			}
			
			//opponenets corners
			if(aBoard.board[0][aBoard.size-1] == 1)
			{
				ofirstCorner = true;
				opponentsCorners++;
			}
			if(aBoard.board[1][aBoard.size-2] == 1)
			{
				 ofirstXsquare = true;
			}
			
			if(aBoard.board[aBoard.size-1][0] == 1)
			{
				opponentsCorners++;
				osecondCorner = true;
			}
			if(aBoard.board[aBoard.size-2][1] == 1)
			{
				secondXsquare = true;
			}
			
			if(aBoard.board[0][0] == 1)
			{
				opponentsCorners++;
				othirdCorner = true;
			}
			if(aBoard.board[1][1] == 1)
			{
				othirdXsquare = true;
			}
			
			if(aBoard.board[aBoard.size-1][aBoard.size-1] == 1)
			{
				opponentsCorners++;
				ofourthCorner = true;
			}
			if(aBoard.board[aBoard.size-2][aBoard.size-2] == 1)
			{
				ofourthXsquare = true;
			}
		
		}
		
		if((firstXsquare && !firstCorner) || (secondXsquare && !secondCorner) || 
				(thirdXsquare && !thirdCorner) || (fourthXsquare && !fourthCorner))
		{
			cornerRating = -60;
		}
		
		if((ofirstXsquare && !ofirstCorner) || (osecondXsquare && !osecondCorner) || 
				(othirdXsquare && !othirdCorner) || (ofourthXsquare && !ofourthCorner))
		{
			cornerRating = 60;
		}
		
		cornerDifference = myCorners - opponentsCorners;
		cornerRating += cornerDifference*5;
		
		//calculate stable rating
		int stableRating = 0;
		int stableDifference= 0;
		if(n.player == 1)
			stableDifference = aBoard.blackStable - aBoard.whiteStable; 
		else
			stableDifference = aBoard.whiteStable - aBoard.blackStable; 
		
		stableRating = stableDifference *2; 
		
		
		int totalSize = aBoard.size * aBoard.size;
		
		
			//difference weights are used depending on what turn it is
			if(aBoard.numPieces > totalSize-6)
			{
			
				boardValue = pieceRating*10 + mobilityRating*2 + stableRating  + cornerRating;
			}
			else if(aBoard.numPieces > 10 && myPieces <=3)
			{
	
				boardValue = pieceRating*4 + mobilityRating*2 + stableRating*5  + cornerRating*5;
			}
			
			else if(aBoard.numPieces > totalSize-(2*aBoard.size))
			{
				boardValue = pieceRating*4 + mobilityRating*3 + stableRating*7  + cornerRating*7;
			}
			else 
			{
				boardValue = pieceRating*-2 + mobilityRating*5 + stableRating*5  + cornerRating*10;
			}
		
		/*int boardValue = 0;
		if(n.player == 1)
		{
			boardValue = n.board.numBlack;
			if(n.board.board[0][0] == 1 || n.board.board[0][n.board.size-1] == 1
					|| n.board.board[n.board.size-1][0] == 1 || 
					n.board.board[n.board.size-1][n.board.size-1] == 1)
				boardValue += 100;
			if(n.board.board[0][0] == -1 || n.board.board[0][n.board.size-1] == -1
					|| n.board.board[n.board.size-1][0] == -1 || 
					n.board.board[n.board.size-1][n.board.size-1] == -1)
				boardValue -= 100;
		}
		else
		{
			boardValue = n.board.numWhite;
			if(n.board.board[0][0] == -1 || n.board.board[0][n.board.size-1] == -1
					|| n.board.board[n.board.size-1][0] == -1 || 
					n.board.board[n.board.size-1][n.board.size-1] == -1)
				boardValue += 100;
			if(n.board.board[0][0] == 1 || n.board.board[0][n.board.size-1] == 1
					|| n.board.board[n.board.size-1][0] == 1 || 
					n.board.board[n.board.size-1][n.board.size-1] == 1)
				boardValue -= 100;
		}*/
			
			//boardValue = Math.abs(boardValue);
		return boardValue;
	}
}
